#pragma once

#include <vector>
#include <queue>
#include <cstdlib>
#include <iostream>

#define BITS_IN_BYTE 8
#define COUNT_OF_BYTES_IN_INT 4

using namespace std;

struct edge{
	int parent, son;
	
	edge(int parent, int son){
		this->parent = parent;
		this->son = son;
	}
};

class IDigraph{
public:
	virtual ~IDigraph(){}

	virtual int get_number_of_vertices() const = 0;
	
	virtual vector<int> get_incidence_list(int vertex) const = 0;
	
	virtual int bytesize() const = 0;
};

class Matrix : public IDigraph{
public:
	Matrix(int vertices, const vector<edge> & Edges){
		matrix.resize(vertices);
		for (int i = 0; i < vertices; i++){
			matrix[i].resize(vertices, 0);
		}
		for (int i = 0; i < Edges.size(); i++){
			matrix[Edges[i].parent][Edges[i].son] = true;
		}
	}
	
	int get_number_of_vertices() const
	{
		return matrix.size();
	}
		
	vector<int> get_incidence_list(int vertex) const
	{
		vector<int> result;
		for (int i = 0; i < matrix[vertex].size(); i++){
			if (matrix[vertex][i]) result.push_back(i);
		}
		return result;
	}
	
	int bytesize() const
	{
		int n = get_number_of_vertices();
		return n * n / BITS_IN_BYTE;
	}
private:
	vector<vector<bool> > matrix;
};

class IncidenceLists : public IDigraph{
public:
	IncidenceLists(int vertices, const vector<edge> & Edges){
		lists.resize(vertices, vector<int>(0));
		for (int i = 0; i < Edges.size(); i++){
			lists[Edges[i].parent].push_back(Edges[i].son);
		}
	}
	
	int get_number_of_vertices() const
	{
		return lists.size();
	}
	
	vector<int> get_incidence_list(int vertex) const
	{
		return lists[vertex];
	}
	
	int bytesize() const
	{
		int ans = 0;
		for (int i = 0; i < lists.size(); i++) ans += lists[i].size();
		return ans * COUNT_OF_BYTES_IN_INT;
	}
private:
	vector<vector<int> > lists;
};

IDigraph* make_compact_digraph(int vertices, const vector<edge> & Edges){		//Edges starts with a big letter because it's a set, not a count
	if (vertices * vertices / BITS_IN_BYTE < Edges.size() * COUNT_OF_BYTES_IN_INT)
	return new Matrix(vertices, Edges); else									//according to rules, edges is just #(Edges) = |Edges| = Edges.size()
	return new IncidenceLists(vertices, Edges);
}

template <class func>
void bfs(const IDigraph& digraph, int vertex, func* make = NULL){
	queue<int> q;	//q means queue, it's used only here
	q.push(vertex);
	vector<bool> used(digraph.get_number_of_vertices(), false);
	while (!q.empty()){
		int cur = q.front();
		q.pop();
		if (used[cur]) continue;
		vector<int> neighbours = digraph.get_incidence_list(cur);
		used[cur] = true;
		for (int i = 0; i < neighbours.size(); i++){
			if (!used[neighbours[i]]) q.push(neighbours[i]);
		}
		if (make) *make(cur);
	}
}

template <class func1, class func2, class func3>
void dfs(const IDigraph& digraph, int vertex = -1, func1 *before = NULL, func2 *after = NULL, func3 *over_edge = NULL){
	vector<int> color(digraph.get_number_of_vertices(), 0);	//0 -- white, 1 -- gray, 2 -- black
	if (vertex > -1){
		vector<int> stack(1, vertex);
		vector<int> last(color.size(), 0);
		vector<vector<int> > incidences(1, digraph.get_incidence_list(vertex));	//if we want to economy memory instead of time, I can not to keep it
		if (before) (*before)(vertex);
		color[vertex] = 1;
		while (!stack.empty()){
			int cur = stack.back();
			if (last[cur] == incidences.back().size()){
				stack.pop_back();
				incidences.pop_back();
				color[cur] = 2;
				if (stack.size() > 0 && over_edge) over_edge->make(stack.back(), cur);
				if (after) (*after)(cur);
			} else {
				int next = incidences.back()[last[cur]++];
				if (color[next] == 0){
					stack.push_back(next);
					incidences.push_back(digraph.get_incidence_list(next));
					color[next] = 1;
					if (before) (*before)(next);
				} else {
					if (over_edge) over_edge->make(cur, next);
				}
			}
		}
	} else {	//start dfs over all graph
		vector<int> stack(0);
		vector<int> last(color.size(), 0);
		vector<vector<int> > incidences(0);
		for (int vertex = 0; vertex < color.size(); vertex++){
			if (color[vertex] == 0){
				if (before) (*before)(vertex);
				color[vertex] = 1;
				stack.push_back(vertex);
				incidences.push_back(digraph.get_incidence_list(vertex));
				while (!stack.empty()){
					int cur = stack.back();
					if (last[cur] == incidences.back().size()){
						stack.pop_back();
						incidences.pop_back();
						color[cur] = 2;
						if (stack.size() > 0 && over_edge) over_edge->make(stack.back(), cur);
						if (after) (*after)(cur);
					} else {
						int next = incidences.back()[last[cur]++];
						if (color[next] == 0){
							stack.push_back(next);
							incidences.push_back(digraph.get_incidence_list(next));
							color[next] = 1;
							if (before) (*before)(next);
						} else {
							if (over_edge) over_edge->make(cur, next);
						}
					}
				}
			}
		}
	}
}

class tarjan{
public:
	tarjan(){}
	
	tarjan(vector<int>* color, vector<int>* stack, vector<int>* time, vector<int>* mintime, vector<char>* busy, int* colors_count, int* current_time){
		this->color = color;
		this->stack = stack;
		this->time = time;
		this->mintime = mintime;
		this->busy = busy;
		this->colors_count = colors_count;
		this->current_time = current_time;
	}
	
	~tarjan(){}
	
	void make(int vertex, int neighbor){
		if ((*busy)[neighbor] == 1){
			(*mintime)[vertex] = min((*mintime)[vertex], (*mintime)[neighbor]);
		}
	}
	
	vector<int>* color;
	vector<int>* stack;
	vector<int>* time;
	vector<int>* mintime;
	vector<char>* busy;
	int* colors_count;
	int* current_time;
};

class func_in : public tarjan {
public:
	func_in(vector<int>* color, vector<int>* stack, vector<int>* time, vector<int>* mintime, vector<char>* busy, int* colors_count, int* current_time){
		this->color = color;
		this->stack = stack;
		this->time = time;
		this->mintime = mintime;
		this->busy = busy;
		this->colors_count = colors_count;
		this->current_time = current_time;
	}
	
	void operator ()(int vertex){
		(*mintime)[vertex] = (*time)[vertex] = ++(*current_time);
		stack->push_back(vertex);
		(*busy)[vertex] = 1;
	}
};

class func_out : public tarjan {
public:
	func_out(vector<int>* color, vector<int>* stack, vector<int>* time, vector<int>* mintime, vector<char>* busy, int* colors_count, int* current_time){
		this->color = color;
		this->stack = stack;
		this->time = time;
		this->mintime = mintime;
		this->busy = busy;
		this->colors_count = colors_count;
		this->current_time = current_time;
	}
	
	void operator ()(int vertex){
		if ((*mintime)[vertex] == (*time)[vertex]){
			while (stack->back() != vertex){
				(*color)[stack->back()] = (*colors_count);
				(*busy)[stack->back()] = 2;
				(*stack).pop_back();
			}
			(*color)[vertex] = (*colors_count);
			(*busy)[vertex] = 2;
			stack->pop_back();
			(*colors_count)++;
		}
	}
};

//this function return the vector of colors of vertices
//where color[u] == color[v] if and only if u and v are in the same strong (or strict) component
//if there exists the second argument v, then this function returns the vector of all vertices in tthe component with v
//in the first case, then if color[u] < color[v] then there is no path from u to v, so it's the topsort too
vector<int> strong_component(const IDigraph& digraph, int vertex = -1){
	int colors_count = 0;
	int current_time = 0;
	int vertices = digraph.get_number_of_vertices();
	vector<int> color(vertices, 0);
	vector<int> stack;
	vector<int> time(vertices, 0);
	vector<int> mintime(vertices, 0);
	vector<char> busy(vertices, 0);
	func_in before(&color, &stack, &time, &mintime, &busy, &colors_count, &current_time);
	func_out after(&color, &stack, &time, &mintime, &busy, &colors_count, &current_time);
	dfs(digraph, -1, &before, &after, &after);
	if (vertex == -1){
		return color;
	} else {
		vector<int> result;
		for (int i = 0; i < vertices; i++){
			if (color[i] == color[vertex]){
				result.push_back(i);
			}
		}
		return result;
	}
}
